class Solution
{
public:
    // O(n)
    int numberOfGoodPartitions(vector<int> &nums)
    {
        unordered_map<int, int> numLastOccur;
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            numLastOccur[nums[i]] = i;
        }
        int nParts = 0;
        int last = 0;
        for (int i = 0; i < n; i++)
        {
            int num = nums[i];
            last = max(last, numLastOccur[num]);
            if (last == i)
            {
                ++nParts;
            }
        }

        // result = 2 ^ (nParts - 1)

        int result = 1;
        for (int i = 0; i < nParts - 1; i++)
        {
            result = (result * 2) % 1000000007;
        }
        return result;
    }

    // O(n^2) 超时
    int numberOfGoodPartitions(vector<int> &nums)
    {
        unordered_map<int, int> numLastOccur;
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            numLastOccur[nums[i]] = i;
        }

        vector<int> cache(n, -1);
        function<int(int)> helper = [&](int begin)
        {
            if (begin == n)
            {
                return 0;
            }
            if (cache[begin] != -1)
            {
                return cache[begin];
            }
            int result = 1;
            int i = begin;
            int last = i;
            while (i < n)
            {
                int num = nums[i];
                last = max(last, numLastOccur[num]);
                if (last == i)
                {
                    result += helper(last + 1);
                    result %= 1000000007;
                }
                i++;
            };
            return cache[begin] = result;
        };

        return helper(0);
    }
};